In data communications, the use of forward error-correction codes plays a fundamental role in transmission accuracy, as well as in increasing spectrum efficiency. Shannon's law suggests that the development of error-correction techniques with increasing coding gain has a limit that arises from the channel capacity. Performances, very close to Shannon's capacity limit, have been obtained using a class of codes, which are widely referred to as “Turbo Codes”.
Generally, Turbo codes are formed using conventional encoders connected either in parallel or series to produce concatenated outputs. The bit sequences passing from one encoder to the next are shifted (or permuted) by an interleaver. This process transforms low-weight codewords into high-weight codewords for the global encoder in order to achieve high coding gains.
Generally, the decoder consists of a network of interconnected de-interleavers and decoding stages, individually matched to the respective constituent codes. The decoding of the received codeword sequences is performed iteratively, using an algorithm that utilizes the a posteriori probability distributions associated to the individual codewords of the transmission sequence. The decoding stages utilize the obtained soft output information (e.g. a reliability vector, a new probability distribution) from the previous decoding stage as a reliability input in the next decoding stage. The decoding process is repeated iteratively until a satisfactory estimate of the transmitted information is achieved.
Since their introduction in 1993, Turbo codes have been successfully applied to many communication areas, especially in wireless personal communication systems, where required data-rate and bit-error-rate are relatively moderate. However, Turbo codes have not been successfully implemented in data storage systems (such as hard discs, and the like) because of the very high data-rate, very stringent bit-error-rate, and the very high complexity of the decoding system. The high complexity can be attributed to the requirement of the soft-input soft-output (SISO) device in the decoder. The complexity is exacerbated by the fact that numerous iterative decoding steps, performed by the SISO device and the Turbo decoder, are required to successfully and accurately decode the Turbo coded information.
The complexity of the SISO device is mainly determined by its trellis structure, and the trellis structure is determined by the channel structure (channel memory length, precoder memory length, etc.). Specifically, the complexity of each SISO device is determined predominantly by the number of possible states in the SISO device. For example, each bit in a binary sequence represents two possible states. A SISO device designed to receive the binary sequence should include 2n states, where n is the number of bits each bit depends upon in the sequence.
The SISO device generally takes a noisy sequence of information and outputs extrinsic information, representing a probability vector associated with the noisy sequence, as well as a less noisy sequence of information. Within the trellis, essentially two symbols are assigned to each branch of the trellis (the information symbol and the coded symbol). Typically, the extrinsic information is passed through an interleaver before being passed to the next SISO in sequence, in order to make the iterative decoding more accurate by introducing weak correlation between the extrinsic information components of the SISO devices, hence each subsequent SISO processes a less correlated sequence. In each iteration, only the extrinsic information generated by each is exchanged between the soft-output decoders. After the last iteration, the final soft-output sequence is decoded at symbol-level.
Generally, the trellis structure is determined by the number of states possible within the SISO device. Thus, when the number of possible states within the SISO device is large, the SISO trellis is correspondingly large and complex. Moreover, the circuit footprint grows according to the trellis size, such that the larger the SISO trellis, the larger the area required on the circuit board to accommodate the SISO device.
It is desirable to perform iterative decoding operations faster and with less complexity, and with only a nominal sacrifice in the bit-error-rates, depending on the application. More specifically, it is desirable to have a decoder that performs the iterative decoding steps with a simpler trellis than ordinarily required by the channel size and precoder length.